package com.gitee.feizns.explore.data_structure.graph;

import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 207. 课程表
 * @author feizns
 * @since 2020/2/27
 */
public class CanFinish {

    static int[][] paths = new int[][]{ {2, 0}, {1, 0}, {3, 1}, {3, 2}, {1, 3} };

    public static void main(String[] args) {
        System.out.println(new CanFinish().canFinish(4, paths));
    }

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        create(prerequisites);
        return dfs(0);
    }

    private Graph<Integer> graph;

    private Set<Integer> cache = new HashSet<>();

    private boolean dfs(int k) {
        if ( cache.contains(k) )
            return false;
        cache.add(k);
        Set<Integer> adj = graph.adj(k);
        for(Integer x : adj) {
            if ( !dfs(x) )
                return false;
        }
        cache.remove(k);
        return true;
    }

    private Graph<Integer> create(int[][] p) {
        graph = new Graph<>();
        for(int[] edge : p)
            graph.addEdge(edge[0], edge[1]);
        return graph;
    }

    public class Graph<K> {

        private Map<K, Set<K>> graph;

        public Graph() {
            graph = new HashMap<>();
        }

        public void addEdge(K s, K t) {
            Set<K> ks = graph.get(s);
            if ( ks == null )
                ks = new HashSet<>();
            ks.add(t);
            graph.put(s, ks);
        }

        public Set<K> adj(K k) {
            Set<K> s = graph.get(k);
            return s != null ? s : Collections.emptySet();
        }

        public Set<K> nodes() {
            return graph.keySet();
        }

    }

}
